package leetcode.N1_N100;

import java.util.Arrays;

/**
 * @author 歪大哥😁
 * @date 2020-06-23.
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 *
 * 示例：
 *
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 *  
 *
 * 提示：
 *
 * 3 <= nums.length <= 10^3
 * -10^3 <= nums[i] <= 10^3
 * -10^4 <= target <= 10^4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum-closest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class N16 {

    public static void main(String[] args) {
        int[] nums = {0,2,1,-3};
        int target = 1;
        System.out.println(threeSumClosest(nums, target));
    }

    /*
    1.排序数组
    2.选取中间三个元素 与 目标值进行比较
    3.根据比较结果决定是左遍历还是右遍历
    4.直到一次遍历前后的值越过目标值，或者遍历到端点，结束遍历
    5.返回最接近的值
     */

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int length = nums.length;
        int valueMid = nums[length/2] + nums[length/2 - 1] + nums[length/2 + 1];
        int closetValue = valueMid;

        if (valueMid < target) {
            // 向右遍历
            for (int i = length / 2 + 1; i < length - 1; i++) {
                int value = nums[i - 1] + nums[i] + nums[i + 1];
                if (value < target) {
                    closetValue = value;
                } else if (value > target) {
                    int oldDelta = Math.abs(closetValue - target);
                    int newDelta = Math.abs(value - target);
                    if (oldDelta > newDelta) {
                        return value;
                    } else {
                        return closetValue;
                    }
                } else {
                    return value;
                }
            }
        } else if (valueMid > target) {
            // 向左遍历
            for (int i = length / 2 - 1; i > 0; i--) {
                int value = nums[i - 1] + nums[i] + nums[i + 1];

                if (value > target) {
                    closetValue = value;
                } else if (value < target) {
                    int oldDelta = Math.abs(closetValue - target);
                    int newDelta = Math.abs(value - target);
                    if (oldDelta > newDelta) {
                        return value;
                    } else {
                        return closetValue;
                    }
                } else {
                    return value;
                }
            }
        }
        return closetValue;
    }




}
